Available today are computer programs known as "road-mapping" programs. Those programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display a map on-screen of the selected location. Today, road-mapping products typically include the ability to calculate a "best route" between two locations. In other words, the user can input two locations, and the road-mapping program will compute the travel directions from the first location to the second location. The directions are typically based on certain user preferences, such as a speed at which the user likes to drive, or the degree of scenery along the route. However, road-mapping programs currently available suffer from significant shortcomings, one of which is the best-route calculation time during which the user must wait.
An algorithm typically used to calculate the optimum (or "best") route between two points in a road network is a variant of a well-known algorithm generally attributed to E. Dijkstra. The computationally intensive part of the algorithm involves calculating a Shortest-Path Spanning Tree ("SPST") for a given point in the road network. Once the SPST has been created, it can be used to quickly generate the shortest path from that point to any other point in the road network. Note that in this sense "shortest" really means "least cost" because each road is assigned a cost or weight not necessarily directly related to the road length. By varying the way the cost is calculated for each road, SPSTs can be generated for the quickest, shortest, or preferred routes.
Each point in the road network can have several corresponding SPSTs. Each road (or "link") in the network can have a different cost, depending on user-defined variables such as the speed at which the user likes to drive. These variables can be generally described as a "driving profile" or a "route type." Accordingly, a single location can have several corresponding SPSTs. Each SPST will provide the best route to any other point in the road network for each set of user-defined variables.
Existing road-mapping programs typically do not begin calculating the best route until after the user has provided all relevant inputs. This is because to complete the calculation, all the user's inputs are required, including the start point, the end point, and the desired route type. In addition, calculating the SPST in the foreground prevents the user from using other features of the program until the calculation is complete. Therefore, existing programs often require that the user first input all route variables before beginning the route calculation. Then, in response to the user's final input, the calculation begins, based on the route type desired, the start point, and the end point. This method can result in a considerable wait for the user during the calculation. The program's other features are typically unavailable to the user during the calculation.
Therefore, a need exists for a system that can more quickly determine a best-route between two points. With such a system there would be less wait-time for the calculation to finish, making the user's experience in interacting with the system more enjoyable.